Image data can often be available in, or convertible into, a vector-graphic form. Vector graphics typically provide discrete, multi-component parametric representations of curves. For example, a pen stroke in simple electronic ink is a plain curve defined by a two-component parametric representation, i.e. a sequence of sample points specified as coordinate pairs. Space curves defined by a three-component parametric representation can be provided, in particular, by advanced graphic tablets sensitive to the distance between pen and the tablet's surface. A number of extra components, representing physical entities other than spatial coordinates, may be provided in addition to parametric representation of a curve. For example, variable-thickness lines drawn by means of pressure-sensitive graphic tablets are plain curves defined by a three-component sequence of samples, in which an extra sample, representing pressure, is added to each pair of coordinate samples.
Quality of vector-graphic data often suffers from noise. For example, visual quality of electronic ink may be affected by combined noise of motor tremor and digitization, especially in hand-held devices. Noise can also result from bitmap-to-vector conversion of image data. In particular, the combination of contour extraction and automatic tracing is known to be a noise intensifying procedure. There are many filtering techniques for denoising image data in vector-graphic form. One common approach is to apply a low-pass digital filter to every component, or to each of selected components, in the sequence of samples.
In addition, vector graphic data typically require reduction in data size. Compression of such data as electronic ink allows to accumulate a useful volume of handwritten notes and drawings in a limited storage and to save time required for data transmission. There are many compression techniques commonly used for vector graphics processing. One typical approach is based on selective discarding of redundant sample points in the original discrete parametric representation of a curve. The excessive sample points can be detected and removed by a trial and error method, in which a sample point is tested whether or not it can be skipped as a knot for polygonal interpolation of a curve.
Another way to eliminate excessive sample points is to start with limited number of critical points, such as cusps and local maxima and minima, as the knots of polygonal interpolation. Such a procedure is described in International Application WO 94/03853 entitled A Method and Apparatus for Compression of Electronic Ink, published on Feb. 17, 1994. This procedure incorporates also denoising and smoothing by digital filtering as a preprocessing, application-specific step. Examples are given of applying triangular, Hanning, or median filters prior to compression.
The compression approach described in International Application WO 94/03853 can be improved using a sequential, segment-by-segment refinement procedure described in U.S. Pat. No. 6,101,280 issued to D. E. Reynolds and entitled Method and Apparatus for Compression of Electronic Ink, in which an additional knot is selected from original points to reduce the deviation of a given segment if needed. As a preprocessing step, a moving average (3-tap rectangular) filter is applied to produce a smoothed version of a curve. The smoothed curve is used to detect critical points and is then abandoned because its shape tends to be significantly distorted.
Shape distortion as a result, of filtering is a major problem in vector graphics processing. For example, in cursive writing, relatively small fragments may be very important for visual perception with respect to both legibility and aesthetic appearance, but noise in electronic ink often creates disturbances that are comparable in size with these critical fragments. Generally, the coordinate signals of handwriting and drawing, and the noise in electronic ink tend to have partially overlapped spectra. When filtering electronic ink, such overlapping tends to cause shape distortion and residual noise. Additional complications may also arise due to high variability in the individual manner of handwriting and in hardware-specific noise. Typically, as a result of low-pass filtering, the sharp cusps in electronic ink are cut, the critical fragments of handwriting are partially lost to smoothing, and handwritten lines look like they are somewhat shrunk in a vertical direction.
A technique addressing the shape distortion problem is disclosed in U.S. application Ser. No. 11/013,869 invented by B. E. Gorbatov et al. and entitled System and Method for Handling Electronic Ink (hereinafter “Gorbatov”), the teachings of which are hereby incorporated by this reference. Gorbatov repeatedly uses a low-pass, smoothing digital filter (instead of polygonal interpolation) for curve reconstruction in the above-mentioned trial and error process of discarding excessive points. In particular, in this curve reconstruction procedure (referred to as upsampling), a recursive low-pass approximation filter is applied to generate a trial version of a curve each time a sample point under testing is removed from the current representation.
It should be noted that during the procedure of discarding excessive points the discrete parametric representation of the curve undergoes certain modifications. In the procedure disclosed in Gorbatov, each next trial sub-sequence of sample points is filtered as a sequence of parametrically equidistant points. It means the new parameter is chosen for each next representation of a curve. These modifications depend on the filter used for curve reconstruction. Hence, the finally obtained representation is adapted to a chosen type of filtering in time (space) domain. Therefore, the process can generally be characterized as curve representation utilizing digital filtering and adaptive parameterization.
Filtering with adaptive parameterization, as described above, allows for better denoising and better visual quality of electronic ink under the same compression ratio requirements. However, in practice, the process is still found to be prone to occasional cusps cutting and some other local distortions.
The previously discussed trial and error process based on polygonal interpolation can also be interpreted as adaptive parameterization, in which parametric representation is adapted for curve reconstruction using piecewise linear interpolation. The same is true for the polygon refinement method disclosed by U.S. Pat. No. 6,101,280 discussed above. There are other data processing methods that allow for parametric representation of a curve being adapted for polynomial or piecewise-polynomial reconstruction. The adaptation is typically achieved by means of an iterative transformation-reparameterization procedure that may use piecewise Discrete Fourier Transform or Discrete Cosine Transform for polynomial approximation and an updatable parameterization table for reparameterization. Such a procedure is disclosed in U.S. Pat. No. 5,473,742 issued to V. G. Polyakov et al. and entitled Method and Apparatus for Representing Image Data Using Polynomial Approximation and Iterative Transformation-Reparameterization Technique.
The transformation-reparameterization procedure is known to be an efficient data compression and curve reconstruction tool. The latter property, for example, is employed in U.S. Pat. No. 6,771,266 issued to Lui et al. and entitled Method and Apparatus for Improving the Appearance of Digitally Represented Handwriting, in which a pen stroke is rendered on the screen as a polyline, and then the transformation-reparameterization procedure of U.S. Pat. No. 5,473,742 is used to refresh the stroke with an improved visual quality.
The transformation-reparameterization procedure, designed primarily as a compression tool rather than a filtering tool, does provide filtering as a concurrent effect, due to transformation part of its transformation-reparameterization cycle. However, because filtering in transform domain is known generally as less flexible and efficient in the majority of real life problems than filtering in time (space) domain, it would be desirable to explore further opportunities for efficient denoising associated with filtering in time (space) domain and adaptive parameterization.
As computing becomes faster and the memory more capacious, there is a higher demand for efficient denoising as part of vector-graphic data processing and, in particular, electronic ink processing. A high subjective quality of denoised data is desired, up to having the resulting images perceived as noiseless and distortion-free.